package com.chunsoft.sort;

import static com.chunsoft.sort.SortUtils.*;

/**
 * Title: QuickSort.java
 * Description: 快速排序
 * Create DateTime: 2023/12/05 00:58
 *
 * @author chunsoft
 */
public class QuickSort {

    /**
     * 快排1.0
     *
     * @param arr 待排序数组
     */
    public static void quickSort1(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process1(arr, 0, arr.length - 1);
    }

    /**
     * 快排1.0 处理器
     *
     * @param arr 待排序数组
     */
    public static void process1(int[] arr, int l, int r) {

        if (l >= r) {
            return;
        }

        int mid = partition(arr, l, r);

        process1(arr, l, mid - 1);
        process1(arr, mid + 1, r);
    }

    public static int partition(int[] arr, int left, int right) {
        if (left > right) {
            return -1;
        }

        if (left == right) {
            return left;
        }

        int index = left;
        int lessEquals = left - 1;
        // 边界条件
        while (index < right) {
            if (arr[index] <= arr[right]) {
                SortUtils.swapNormal(arr, index, ++lessEquals);
            }
            index++;
        }

        SortUtils.swapNormal(arr, ++lessEquals, right);

        return lessEquals;
    }

    /**
     * 快排2.0
     * mid 荷兰国旗问题，相等的都不处理
     *
     * @param arr 待排序数组
     */
    public static void quickSort2(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process2(arr, 0, arr.length - 1);
    }

    public static void process2(int[] arr, int l, int r) {
        if (l >= r) {
            return;
        }

        int[] mid = partition2(arr, l, r);

        process2(arr, l, mid[0] - 1);
        process2(arr, mid[1] + 1, r);
    }

    public static int[] partition2(int[] arr, int left, int right) {
        if (left > right) {
            return new int[]{-1, -1};
        }

        if (left == right) {
            return new int[]{left, right};
        }

        int index = left;
        int leftEquals = left - 1;
        int rightEquals = right;
        // 边界条件
        while (index < rightEquals) {
            if (arr[index] == arr[right]) {
                index++;
            } else if (arr[index] < arr[right]) {
                swapNormal(arr, index++, ++leftEquals);
            } else {
                swapNormal(arr, index, --rightEquals);
            }
        }

        SortUtils.swapNormal(arr, rightEquals, right);

        return new int[]{leftEquals + 1, rightEquals};
    }

    /**
     * 快排3.0
     *
     * @param arr 待排序数组
     */
    public static void quickSort3(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process3(arr, 0, arr.length - 1);
    }

    public static void process3(int[] arr, int l, int r) {
        if (l >= r) {
            return;
        }

        swapNormal(arr, l + (int) (Math.random() * (r - l + 1)), r);

        int[] mid = partition2(arr, l, r);

        process3(arr, l, mid[0] - 1);
        process3(arr, mid[1] + 1, r);
    }

    public static void main(String[] args) {
        int testTime = 5;
        int maxSize = 100;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            printArray(arr1);
            int[] arr2 = copyArray(arr1);
            quickSort3(arr1);
            printArray(arr1);
            comparator(arr2);
            printArray(arr2);
            if (!isEqual(arr1, arr2)) {
                succeed = false;
                break;
            }
        }
        System.out.println("验证结果：" + succeed);
    }
}
